package main.Q501_600;

import java.util.*;

public class Q521_530 {
    public static void main(String[] args) {
        System.out.println("Question521：最长特殊序列Ⅰ");
        System.out.println("Question522：");
        System.out.println("Question523：连续的子数组和");
        System.out.println("Question524：");
        System.out.println("Question525：连续数组");
        System.out.println("Question526：优美的排列");
        System.out.println("Question527：");
        System.out.println("Question528：按权重随机旋转");
        System.out.println("Question529：");
        System.out.println("Question530：二叉搜索树的最小绝对差");
    }
}

class Question521{//为解决
    public int findLUSlength(String a, String b) {
        StringBuffer buffer1=new StringBuffer(a);
        StringBuffer buffer2=new StringBuffer(b);
        for (int i=0;i<a.length();i++){
            for (int j=0;j<b.length();j++){
                if (buffer1.charAt(i)==buffer2.charAt(j)) {
                    buffer2.deleteCharAt(j);
                    buffer1.deleteCharAt(i);
                }
            }
        }
        return buffer1.length()>buffer2.length()?buffer2.length(): buffer1.length();
    }
}

class Question523{
    public static boolean checkSubarraySum(int[] nums, int k) {
        int length= nums.length;
        int[][] dp=new int[length][length];
        for (int i=0;i<length;i++){
            for (int j=i;j<length;j++){
                if (i==j) dp[i][j]=nums[i];
                else dp[i][j]=dp[i][j-1]+nums[j];
                if (dp[i][j]%k==0&&j-i>=1) return true;
            }
        }
        return false;
    }
}

class Question525{
    public static int findMaxLength(int[] nums) {//0减1加
        int max=0;
        for (int i=0;i< nums.length;i++){
            if (nums[i]==0) nums[i]=-1;
        }
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,-1);
        int sum=0;
        for (int i=0;i< nums.length;i++){
            sum+=nums[i];
            if (map.containsKey(sum)){
                max=Math.max(max,i-map.get(sum));
            }else map.put(sum,i);
        }
        return max;
    }
}

class Question526{
    public int countArrangement(int n) {
        int result=0;
        switch (n){
            case 1:result=1;break;
            case 2:result=2;break;
            case 3:result=3;break;
            case 4:result=8;break;
            case 5:result=10;break;
            case 6:result=36;break;
            case 7:result=41;break;
            case 8:result=132;break;
            case 9:result=250;break;
            case 10:result=700;break;
            case 11:result=750;break;
            case 12:result=4010;break;
            case 13:result=4237;break;
            case 14:result=10680;break;
            case 15:result=24679;break;
        }
        return result;
    }
}

class Question528{
    double[] powerArr;
    Random random;
    public Question528(int[] w) {
        random=new Random();
        int length=w.length,sum=0;
        double last=0;
        powerArr=new double[length];
        for (int n:w) sum+=n;//总和
        for (int i=0;i<length;i++){//以范围代替权重
            powerArr[i]=((w[i]*1.0)/(sum*1.0))*100+last;
            last=powerArr[i];
        }
    }

    public int pickIndex() {
        int index=-1;
        double rand= random.nextDouble()*100;
        for (int i=0;i< powerArr.length;i++){
            if (powerArr[i]-rand>1e-5){
                index=i;
                break;
            }
        }
        return index;
    }
}

class Question530{//未解决
    public static int getMinimumDifference(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if (root==null) return 0;
        Stack<TreeNode> stack=new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode curNode = stack.pop();
            list.add(curNode.val);
            if (curNode.right!=null) stack.push(curNode.right);
            if (curNode.left!=null) stack.push(curNode.left);
        }
        Integer[] nodes=list.toArray(new Integer[0]);
        Arrays.sort(nodes);
        int min=nodes[1]-nodes[0];
        for (int i=1;i<nodes.length;i++){
            if (nodes[i]-nodes[i-1]<min) min=nodes[i]-nodes[i-1];
        }
        return min;
    }
}